#include <iostream>
#include <utility>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
#define N 100

struct Token
{
	string value;
	string type;
};

struct Production {
	string prod_l;
	string prod_r;
	string prod;
};

class Item {
public:
	string prod;
	int pos; // ·在产生式中的位置 A->·E：0、A->E·E：1
	vector<string> symbol;// 搜索符

	Item(const string& prod, int pos, const vector<string>& symbol)
		: prod(prod), pos(pos), symbol(symbol) {
	}

	bool operator==(const Item& other) const {
		return prod == other.prod && pos == other.pos && symbol == other.symbol;
	}

	bool operator!=(const Item& other) const {
		return !(*this == other);
	}
};

//struct PairItemHash {
//	template <typename T1, typename T2>
//	size_t operator()(const pair<T1, T2>& p) const {
//		size_t h1 = hash<T1>{}(p.first);
//		size_t h2 = 0;
//		for (const auto& item : p.second) {
//			h2 ^= hash<T2>{}(item)+0x9e3779b9 + (h2 << 6) + (h2 >> 2);
//		}
//		return h1 ^ (h2 << 1);
//	}
//};

struct PairItemEqual {
	template <typename T1, typename T2>
	bool operator ()(const pair<T1, T2>& p1, const pair<T1, T2>& p2) const {
		return p1.first == p2.first && p1.second == p2.second;
	}
};

class Parser {
public:
	void LoadCFG();
	void LoadInputFile();
	void LR1_ItemSets();
	void LL1_Output();
	void LR1_Output();
	void AddTransition(const pair<int, vector<Item>>& from, const string& symbol, const pair<int, vector<Item>>& to);
	int LL1_Table(int stackTop, int TokensTop);
	int LR1_GotoTable(pair<int, vector<Item>> itemSet, string symbol);
	int StackPush(int* top, Production prod);
	bool IsTerminal(int* top);
	pair<string, int> LR1_ActionTable(pair<int, vector<Item>> itemSet, string symbol);

	int itemSetNum; //项目集个数
	vector<string> V_T;
	vector<string> V_N;
	vector<string> stack;
	vector<Token> Tokens;
	pair<int,vector<Item>> ItemSet;// I0、I1、I2...,int为序号
	vector<pair<int, vector<Item>>> ItemSets; //项目集族
	//unordered_map<pair<int, vector<Item>>, unordered_map<string, pair<int, vector<Item>>>, PairItemHash, PairItemEqual> transitions;
	Production productions[24];
};

void Parser::LoadInputFile() {
	fstream file;
	int i = 0;
	file.open("tokens_input.txt", ios::in);

	if (!file)
	{
		cout << "no program file available\n";
		system("pause");
		exit(0);
	}

	string tmp;
	Token t;
	while (!file.eof())
	{
		char ch = file.get();
		if (ch != '\t' && ch != '\n') {
			tmp += ch;
		}
		else if (ch == '\t') {
			t.value = tmp;
			tmp.clear();
		}
		else {
			t.type = tmp;
			tmp.clear();
			Tokens.push_back(t);
		}
	}
	t.type = tmp;
	Tokens.push_back(t);
}

void Parser::LoadCFG(){
	fstream file;
	file.open("CFG.txt", ios::in);

	if (!file)
	{
		cout << "no CFG file available\n";
		system("pause");
		exit(0);
	}

	string preproductions;
	while (!file.eof())
	{
		preproductions += file.get();
	}
	preproductions.pop_back();

	istringstream stream(preproductions);
	vector<string> v;
	string temp;

	while (getline(stream, temp)) {
		v.push_back(temp);
	}
	int idx = 0;
	string connect = " -> ";
	int start;
	string head;
	int substart;
	for (int i = 0; i < v.size(); i++) {
		string t = v[i];
		int j = 0;
		start = 0;
		while (j < t.length()) {
			if (t[j] == '-' && t[j + 1] == '>') {
				head = t.substr(0, j - 1);
				V_N.push_back(head);
				start = j + 3;
				j = j + 3;
				continue;
			}
			string substring;
			if (t[j] == '|') {
				substring = t.substr(start, j - 1 - start);
				productions[idx].prod_l = head;
				substart = 0;
				for (int k = 0; k < substring.length(); k++) {
					if (substring[k] >= 'A' && substring[k] << 'Z') {
						substart = -1;
						continue;
					}
					else if (substring[k] == ' ' && substart < 0) {
						substart = k+1;
					}
					else {
						V_T.push_back(substring.substr(substart, k - substart));
						substart = -1;
					}
				}
				productions[idx].prod_r = substring;
				productions[idx].prod = head + connect + substring;
				idx++;
				start = j + 2;
			}
			j++;
			if (j < start) { j = start; }
		}
		productions[idx].prod_l = head;
		productions[idx].prod_r = t.substr(start);
		productions[idx].prod = head + connect + t.substr(start);
		idx++;
	}
}

//void Parser::AddTransition(const pair<int, vector<Item>>& from, const string& symbol, const pair<int, vector<Item>>& to) {
//	transitions[from][symbol] = to;
//}

void Parser::LR1_ItemSets() {

}

int Parser::LL1_Table(int stackTop, int TokensTop){
	if (stack[stackTop] == "P") {
		return 0;
	}
	else if (stack[stackTop] == "L") {
		return 1;
	}
	else if (stack[stackTop] == "D") {
		if (Tokens[TokensTop].value == "#") {
			return 2;
		}
		else if (Tokens[TokensTop].value == "using") {
			return 3;
		}
		else {
			return 4;
		}
	}
	else if (stack[stackTop] == "M") {
		return 5;
	}
	else if (stack[stackTop] == "S") {
		return 6;
	}
	else if (stack[stackTop] == "T") {
		return 7;
	}
	else if (stack[stackTop] == "N") {
		return 8;
	}
	else if (stack[stackTop] == "A") {
		if (Tokens[TokensTop].value == ")") {
			return 10;
		}
		else {
			return 9;
		}
	}
	else if (stack[stackTop] == "C") {
		return 11;
	}
	else if (stack[stackTop] == "B") {
		return 12;
	}
	else if (stack[stackTop] == "E") {
		return 13;
	}
	else if (stack[stackTop] == "F") {
		if (Tokens[TokensTop].type == "NUMBER") {
			return 15;
		}
		else if (Tokens[TokensTop].type == "IDENTIFIER") {
			return 14;
		}
	}
	else if (stack[stackTop] == "O") {
		if (Tokens[TokensTop].value == "+") {
			return 16;
		}
		else {
			return 17;
		}
	}
	else {
		cout << "语法错误";
	}
	return -1;
}

pair<string, int> Parser::LR1_ActionTable(pair<int, vector<Item>> itemSet, string symbol) {
	return make_pair("reduce", 5);
}

//int Parser::LR1_GotoTable(pair<int, vector<Item>> itemSet,string symbol) {
//	vector<Item> to;
//	auto outerIt = transitions.find(itemSet);
//	if (outerIt != transitions.end()) {
//		auto innerIt = outerIt->second.find(symbol);
//		if (innerIt != outerIt->second.end()) {
//			return innerIt->second.first;
//		}
//	}
//	return 0;
//}

int Parser::StackPush(int* top, Production production){
	int i;
	const string c = "ε";

	if (production.prod_r == c)
	{
		stack.pop_back();
	}
	else {
		stack.pop_back();
		string tmp;
		tmp = production.prod_r;
		int start;
		string subtmp;
		start = tmp.length() - 1;
		for (int j = tmp.length()-1; j >= 0; j--) {
			if (tmp[j] == ' ') {
				subtmp = tmp.substr(j + 1, start - j);
				stack.push_back(subtmp);
				start = j - 1;
			}
		}
		stack.push_back(tmp.substr(0, start+1));
	}

	*top = stack.size() - 1;
	return 0;
}

bool Parser::IsTerminal(int* top){
	if (stack[(*top)] == Tokens[0].value) {
		stack.pop_back();
		(*top)--;
		Tokens.erase(Tokens.begin());
		return true;
	}
	else if (Tokens[0].type == "NUMBER") {
		if (stack[(*top)] == "num") {
			stack.pop_back();
			(*top)--;
			Tokens.erase(Tokens.begin());
			return true;
		}
	}
	else if (Tokens[0].type == "IDENTIFIER") {
		if (stack[(*top)] == "id") {
			stack.pop_back();
			(*top)--;
			Tokens.erase(Tokens.begin());
			return true;
		}
	}
	else if (Tokens[0].type == "KEYWORD") {
		if (stack[(*top)] == "type") {
			stack.pop_back();
			(*top)--;
			Tokens.erase(Tokens.begin());
			return true;
		}
	}
	else{
		return false;
	}
}

void Parser::LL1_Output(){
	fstream f;
	f.open("LL(1) output.txt", ios::out);

	int stackTop = 1;
	int TokensTop = 0;
	int i;
	int idx = 0;
	int len;

	while(Tokens.size()>0)
	{
		f << "第 " << ++idx << " 步:  \t";
		f << "栈: ";
		len = 0;
		for (int j = 0; j < stack.size(); j++) {
			f << stack[j];
			len += stack[j].length();
		}
		f << "\t";
		if (len < 12) {
			f << "\t";
			if (len < 4) {
				f << "\t";
			}
		}
		if (Tokens.size() == 1) {
			f << "输入: " << Tokens[0].value << "  \t\t";
		}
		else {
			f << "输入: " << Tokens[0].value << " ...\t";
			if (Tokens[0].value.length() < 6) {
				f << "\t";
			}
		}
		if (IsTerminal(&stackTop)) {
			f <<"终结符，匹配成功" << endl;
		}
		else {
			i = LL1_Table(stackTop, TokensTop);
			StackPush(&stackTop, productions[i]);
			f << "下一步所用产生式: " << productions[i].prod << endl;
		}
	}
	f << "LL(1)分析完成" << endl;
	f.close();
}

void Parser::LR1_Output() {
	fstream f;
	f.open("LR(1) output.txt", ios::out);

	int state=0;

	while (Tokens.size() > 0) {

	}
	f.close();
}

int main()
{
	Parser PA;

	PA.LoadCFG();
	PA.stack.push_back("$");
	PA.stack.push_back("P");

	PA.LoadInputFile();
	PA.LL1_Output();
	/*PA.LR1_Output(); */

	return 0;
}